﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Brainee.Search;

namespace Brainee.Examples.Search
{
  /// <summary>
  /// The 8-puzzle, consists of a 3 x 3 board with eight numbered tiles and a blank space. A tile
  /// adjacent to the blank space can slide into the space. The object is to reach a specified goal
  /// state, such as the one shown on the right of the figure. 
  /// 
  ///  +---+---+---+          +---+---+---+
  ///  | 7 | 2 | 4 |          |   | 1 | 2 |
  ///  +---+---+---+          +---+---+---+
  ///  | 5 |   | 6 |   ===>   | 3 | 4 | 5 |
  ///  +---+---+---+          +---+---+---+
  ///  | 8 | 3 | 1 |          | 6 | 7 | 8 |
  ///  +---+---+---+          +---+---+---+
  /// 
  /// The standard formulation is as follows:
  ///   - States: A state description specifies the location of each of the eight tiles and the blank
  ///     in one of the nine squares.
  ///   - Initial state: Any state can be designated as the initial state. Note that any given goal
  ///     can be reached from exactly half of the possible initial states.
  ///   - Successor function: This generates the legal states that result from trying the four
  ///     actions (blank moves Left, Right, Up, or Down).
  ///   - Goal test: This checks whether the state matches the goal configuration shown in Figure
  ///     3.4. (Other goal configurations are possible.)
  ///   - Path cost: Each step costs 1, so the path cost is the number of steps in the path.
  /// </summary>
  public class EightPuzzle : IProblem
  {
    private readonly int _size = 9;

#region States

    public class State : IState
    {
      public byte [] Tiles { get; private set; }
      public int Blank { get; private set; }

      public State (byte [] tiles)
      {
        Tiles = tiles;
        Blank = Array.FindIndex (tiles, b => b == 0);
      }

      public State (byte [] tiles, int swap)
        : this(tiles)
      {
        Tiles [Blank] = Tiles [swap];
        Tiles [swap] = 0;
        Blank = swap;
      }
    }

    private class StateEqualityComparer : IEqualityComparer<IState>
    {
      public bool Equals (IState x, IState y)
      {
        return ((State)x).Tiles.SequenceEqual(((State)y).Tiles);
      }

      public int GetHashCode (IState obj)
      {
        return ((State)obj).Tiles.Aggregate ((a, b) => (byte)(a ^ b));
      }
    }

#endregion
#region Actions

    public class Actions : IAction
    {
      public class LeftAction : Actions { }
      public static readonly LeftAction Left = new LeftAction ();

      public class RightAction : Actions { }
      public static readonly RightAction Right = new RightAction ();

      public class UpAction : Actions { }
      public static readonly UpAction Up = new UpAction ();

      public class DownAction : Actions { }
      public static readonly DownAction Down = new DownAction ();
    }

#endregion
#region IProblem implementation

    public IState InitialState { get; set; }

    public IEqualityComparer<IState> StateComparer
    {
      get { return new StateEqualityComparer (); }
    }

    public IEnumerable<ActionState> Successors (IState state)
    {
      State s = state as State;
      if (s == null)
        throw new ArgumentException ();

      List<ActionState> successors = new List<ActionState> ();

      int col = s.Blank % 3;
      int row = s.Blank / 3;
      
      if (col != 2)
        successors.Add (new ActionState(Actions.Right, new State ((byte[])s.Tiles.Clone(), s.Blank + 1)));
      if (col != 0)
        successors.Add (new ActionState(Actions.Left, new State ((byte[])s.Tiles.Clone (), s.Blank - 1)));

      if (row != 2)
        successors.Add (new ActionState(Actions.Down, new State ((byte[])s.Tiles.Clone (), s.Blank + 3)));
      if (row != 0)
        successors.Add (new ActionState (Actions.Up, new State ((byte [])s.Tiles.Clone (), s.Blank - 3)));

      return successors;
    }

    public bool GoalTest (IState state)
    {
      for (int i = 0; i < _size; i++)
      {
        if ((state as State).Tiles [i] != i)
          return false;
      }
      return true;
    }

    public double EstimatedCostToGoal (IState state)
    {
      throw new NotImplementedException ();
    }

    public double StepCost (IState from, IAction action, IState to)
    {
      return 1.0;
    }

#endregion
  }
}
